In a remote electronic voting or poll system, a plurality of authorized voters cast their vote or opinion from given vote casting devices to a virtual voting centre, through a communication network. A server or a plurality of them constitute that virtual polling station and they are responsible for accepting connections from voters and recording their votes or opinion issued for their further Tallying and tabulation. After they are tabulated, the results of the poll are finally published, probably through the communication network itself.
It is clear that some safety features must be included in this kind of remote electronic voting systems. Voting in the traditional way (i.e. casting a physical ballot at a true polling station) is done with confidence because of the use of physical safety measures such as paper envelopes, guards, or physical ballot boxes. However, these kinds of measures for the physical protections are no longer useful in remote electronic voting systems. They must be replaced by suitable digital security measures, a task which involves complex problems, with a set of specific safety requirements. The voter's privacy, for example, is a central safety requirement at any electoral process and in many kinds of polls. Nobody (not even the electoral authorities nor the administrators of the voting serves) must be capable of correlating the voters with the votes cast. However, when casting their vote, the voters must be suitably identified through some authentication mechanism to prevent that non authorized voters vote or that authorized voters vote more than once. The accuracy of the results is also very important. Nobody must be capable of adding false ballots (may be in the name of the voters who abstained to vote), nor to erase or manipulate the valid votes cast. Another quality wished is the secrecy on any intermediate result while the poll is not complete, unless the characteristics of the process requires otherwise. The object of said secrecy is to prevent that the current state of the poll could affect the decision of some voters. Another very important safety requirement is to verify the final results. The voters must be capable of verifying that their respective votes have been correctly recorded. In the event of detecting any problem in the recount, the voters involved must be able to publicly evidence (without interfering with their privacy so doing) that their validated votes were not correctly treated. Lastly, the use of electronic voting systems must not expose the voters to coercion nor either facilitate sale of votes.
This kind of specific safety requirements for an electoral process cannot be solved only with the use of generic digital security measures current in the market, such as firewalls, demilitarized areas, coding of the data at the transfer level, etc. A correct solution must necessarily include a special purpose cryptographic scheme specifically designed for the problems that a remote electronic voting imposes. A cryptographic voting scheme accurately determines the steps and actions involved in the remote vote casting as well by the device issuing the votes used by the voter as by the corresponding voting server. The scheme also determines the cryptographic operations which must occur during the process of vote tallying and also for verifying the final results. Of course, a cryptographic voting scheme must also be completed with generic safety measures to maximise the safety and to best protect the full voting system.
The first cryptographic voting scheme was proposed by Chaum in 1981 (Chaum, D. Untraceable electronic mail, return addresses and digital pseudonyms. Communications of the ACM, v.24, n.2, pp. 84-88, 1981). Many other proposals followed, giving a large group of voting schemes, known as schemes based on mixing techniques or mixing. The fundamental principle of these schemes based on mixing consisted in casting votes to a virtual polling station through some kind of anonymous channel constructed in the communication network. Usually, said voting schemes used the technique of the blind digital signature disclosed in U.S. Pat. No. 4,759,063, to validate the votes without impairing the voters privacy. Among the voting schemes based on mixing, the most representative examples were disclosed in [Fujioka, A., Okamoto, T. & Ohta, K. A practical secret voting scheme for large scale elections. Proc. of Auscrypt '92, LNCS 718, pp. 244-251, 1992] and [Park, C., Itoh, K. & Kurosawa, K. efficient anonymous channel and all/nothing election scheme. Proc. of Eurocrypt '93, LNCS 765, pp. 248-259, 1993]. The invention disclosed in U.S. Pat. No. 6,317,833 is also based on mixing although in contrast with above mentioned proposals, the mixing process is not carried out in the communication channel but in the vote receiving centre. The voters protect their votes with the public key owned by the voting authority. Said authority is very similar to the character of the Electoral Board disclosed in [Borrell, J. Rifá, J. An implementable secure voting scheme. Computers & Security, 15, pp. 327-338, 1996]. Each voter requires a pair of asymmetric keys in order to sign the coded vote. In the description of the invention, it is only referred to the cryptosystem ElGamal [ElGamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms, Proc. of Crypto '84, LNCS 196, pp 10-18, 1985] as a means for said signature. It is then assumed that the pair of keys of each voter is to be brought in line with the cryptosystem ElGamal. Said requirement means a limitation in the voting scheme. In addition, the scheme does not offer any important benefit: the verifiability or the possibility that the voters verify the correct record of their votes when the process is complete.
A second group of cryptographic voting schemes, based on homomorphic coding techniques, was started with the work by Benaloh and Yung on 1986 [Benaloh, J. C. & Yung, M. Distributing the power of a government to enhance the privacy of voters. Proc. of 5th Annual ACM Symposium on Principles of Distributed Computing, pp. 52-62, 1986]. These voting schemes avoided the use of anonymous channels by splitting individual votes into a number of pieces and sending each piece to a separate Tallying agent. Said agents counted the votes without the need of decoding them (for this they accounted on cryptographic mechanisms which secured the accurateness of the recount). Some representative examples of voting schemes based on homomorphic coding techniques have been recently proposed in [Sako, K. & Kilian, J. Secure voting using partially compatible homomorphisms. Proc. of Crypto '94, LNCS 839, pp. 411-424, 1994], [Cramer, R., Franklin, M., Schoenmakers, B. & Yung, M. Multi-authority secret-ballot elections with linear work. Proc. of Eurocrypt '96, LNCS 1070, pp. 72-83, 1996] and [Cramer, R., Gennaro, R. & Schoenmakers, B. A secure and optimally efficient multi-authority election scheme. Proc. of Eurocrypt '97, LNCS 1233, pp. 103-118, 1997]. The inventions of U.S. Pat. No. 5,495,532 and WO 0120562 both disclose voting schemes based on homomorphic coding techniques. Said schemes require computing resources significantly greater than those required for the schemes based on mixing, making impossible they are implemented in client devices having a low computing capacity. Another limitation to said schemes is that, due to their intrinsic characteristics they result absolutely incapable of supporting ballots having arbitrary formats.
Inventions U.S. Pat. No. 6,081,793 and U.S. Pat. No. 6,021,200 disclose rather simplistic cryptographic voting schemes based on the known “two-agency model”. In general, these two voting schemes provides a solution to the safety requirements of elections only in the event that both agencies do not join in an unfair coalition and, in addition, it is necessary to place full confidence in some of the parts of the system. In the U.S. Pat. No. 6,081,793 the model uses an authenticator during the ballot casting process to detach the voter authentication of the encrypted ballot to prevent any vote-voter correlation of the results. This implementation has the limitation that the result counter needs to put trust in the authenticator, because the counter cannot check by itself that the ballot contents belong to a valid voter. In addition invention voters doesn't have a voting receipt to check the voting results. The method checks during the voting process that the ballot has been received by the authenticator. But this check doesn't provide to the voter a voting receipt to verify if the votes were received by the counter when it starts the counting process or so far.
In any cryptographic voting scheme, measures have to be taken designed to guarantee the verifiability of the final result of the vote cast by the voters and at same time measures for protecting against coercion to the voter by third parties as well as against the sale of votes by the voters themselves. The two sets of measures evidenced to be contradictory to each other. In fact, by facilitating the verifiability, the possibility of coercion and sale of votes is increased and if the possibility of coercion and the sale of votes is hindered the verifiability is also hindered. Two prior works simultaneously tried to overcome the two questions, although the proposals resulting from them are not implementable on regular communication networks. In U.S. Pat. No. 6,092,051 and EP1017025, voting cryptographic segments are disclosed which use an anonymous channel as the one disclosed in U.S. Pat. No. 5,682,430. Said channel must be physically protected against passive assailants who can steal information therefrom therefore the resulting voting systems cannot employ conventional data communication networks such as Internet.